package com.github.kezhenxu94.playground.java.interview.tencent;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 算法基础-字符移位
 *
 * 小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，
 * 各个字符的相对位置不变，且不能申请额外的空间。
 * 你能帮帮小Q吗？
 *
 * 输入描述:
 *
 * 输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
 *
 *   输出描述:
 *
 *   对于每组数据，输出移位后的字符串。
 *
 *   输入例子:
 *   AkleBiCeilD
 *
 *   输出例子:
 *   kleieilABCD
 */
public class TencentCharShift {

	public static void main(String[] args) throws Exception {
		TencentCharShift sol = new TencentCharShift();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (String line = br.readLine(); line != null; line = br.readLine())
		System.out.println(sol.charShift(line));
	}

	public String charShift(String str) {
		int lastLowerCase = str.length() - 1;
		char[] chars = str.toCharArray();
		while (Character.isUpperCase(chars[lastLowerCase]))
			lastLowerCase--;
		for (int i = lastLowerCase; i >= 0; i--) {
			if (Character.isUpperCase(chars[i])) {
				char temp = chars[i];
				for (int j = i; j < lastLowerCase; j++)
					chars[j] = chars[j + 1];
				chars[lastLowerCase--] = temp;
				i = lastLowerCase;
			}
		}
		return new String(chars);
	}
}
